package Hot100.Stack;

import java.util.Deque;
import java.util.Map;
import java.util.Stack;

public class largestRectangleArea {
    public static void main(String[] args) {
        int heights[] = {2,1,5,6,2,3};
        System.out.println(new largestRectangleArea().largestRectangleArea(heights));
    }
    public int largestRectangleArea(int[] heights) {
        int result = 0;
        int height[] = new int[heights.length + 2];
        height[0] = 0;
        height[height.length - 1] = 0;
        //创建一个新的height数组
        for (int i = 0; i < heights.length; i++) {
            height[i + 1] = heights[i];
        }

        //stack 存的是height的元素下标
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            while (height[i] < height[stack.peek()]){
                int mid = stack.pop();
                int w = i - stack.peek() - 1;
                int h = height[mid];
                result = Math.max(result,w*h);
            }
            stack.push(i);
        }
        return result;
    }
}
